/*
 * @lc app=leetcode.cn id=135 lang=cpp
 *
 * [135] 分发糖果
 */

// @lc code=start
class Solution
{
public:
    int candy(vector<int> &ratings)
    {
        //这道题就是比较典型的贪心算法 因为如果考虑全局最优的话 很难做得出来
        //局部最优 两次遍历 从前往后 如果后面的分高糖果数一定大 在从后往前
        vector<int> candies(ratings.size(), 1);
        //为什么从右往左需要从右开始是因为需要利用第一次从左到右的结果
        //从左到右  左<右
        for (int i = 0; i < ratings.size() - 1; i++)
        {
            if (ratings[i] > ratings[i + 1])
            {
                candies[i] = candies[i + 1] + 1;
            }
        }
        //从右往左 right<left
        for (int i = ratings.size() - 2; i >= 0; i--)
        {
            if (ratings[i + 1] > ratings[i])
            {
                candies[i + 1] = max(candies[i + 1], candies[i] + 1);
            }
        }
        int res = 0;
        for (int i = 0; i < candies.size(); i++)
        {
            res += candies[i];
        }
        return res;
    }
};
// @lc code=end
